RS推荐系统

#RS推荐系统| 来源: 网络整理| 查看: 265

什么是最近邻查找？

在推荐系统中，主要分为召回跟排序两个阶段。

召回阶段，基于用户画像及场景数据从海量的视频库（百万级别）中将相关度最高的资源检索出来，作为候选集，召回阶段可以通过“粗糙”的方式召回候选item。排序阶段，基于更加精细的特征对候选集（百级别）进行排序，最终呈现给用户的是很少的一部分数据。在这个ranking阶段，采用更精细的特征计算user-item之间的排序score，作为最终输出推荐结果的依据。

随着机器学习的发展，越来越多问题转移到deep learning上面解决，而系统实际部署在基于Tensorflow的Google Brain上，模型有接近10亿级参数，训练样本千亿级别。所以，如此之大数量级的数据量，如果要通过常规方法，计算item两两之间的相似度，那么计算量级要到（n^2）级别，实在是太久了。针对这一现象，聪明的人类提出了NN的方法：在这里插入图片描述

NN，Nearest Neighbor Search，最近邻查找问题。KNN，K-Nearest Neighbor，k最近邻，查找离目标数据最近的前k个数据项。ANN，Approximate Nearest Neighbor，近似最近邻检索，在牺牲可接受范围内的精度的情况下提高检索效率。ANN，Approximate Nearest Neighbor，近似最近邻检索，在牺牲可接受范围内的精度的情况下提高检索效率。LSH，局部敏感哈希是ANN的一种。什么是Hash？

目前主流的索引技术有：

基于树的索引技术（二叉树，B-Tree,B+Tree）基于哈希的索引技术基于词的倒排索引

海量数据的检索方式，Hash是重要的索引技术。所谓hash，简而言之，就是将原始数据通过一个函数（hash）映射到新的数值。比如自定义一个hash 2 x + 1 2x+1 2x+1，原始数据有[2,4,6,8]，通过hash可以映射到[5,9,13,17]。

针对海量且高维的数据如何进行查找：

如果数据是低维 and 小数据 => 通过线性的方式查找。数据不仅海量，而且高维 => 需要降维，采用索引方式查找

LSH，Locality-Sensitive Hashing，局部敏感哈希

需要查找与某个数据1个或多个相似的数据。最近邻查找方法（ANN，Approximate Nearest Neighbor）在这里插入图片描述

对于传统的HashTable用于检索数据，无法将相似的数据放到同一个Bucket中，比如h=x mod wLSH将相邻的数据，通过映射后依然保持相邻的关系，即保持局部的敏感度Locality-Sensitive。通过Hash Function，每个Bucket会落入一些原始数据，属于同一个桶内的数据有很大可能是相邻的（也存在不相邻的数据被hash到了同一个桶内）。将原始数据集合分成了多个子集合（即每个bucket），每个子集合中的数据大概率是相邻的，而且子集合中的元素个数较少。方便进行近邻查找 => 在一个很小的集合里查找相邻元素

上面提到即使是相邻的元素，也有可能分到不同的bucket，下面举个栗子~： $$ Hash(127) = 127%8 = 7; Hash(123) = 123%8 = 3; Hash(1023) = 1023%8 = 7;

$$ 从上面的例子可以看出通过hash把127和1023分到了同一个桶7，而与127更加相邻的123却分到了桶3。所以LSH一定程度上会丢失精度，但是精度换时间，这种买卖的交易是值得的。

MiniHash算法

在计算文本相似度中，有：

k-shingle，也称为k-gram，文档中任意长度为k的字符串。将每篇文档可以表示成文档中出现一次或者多次的k-shingle的集合比如document=“abcdabd”，当2-shingle组成的集合为 {ab,bc,cd,da,bd}如果两个文档相似，那么他们会有很多的shingles也是相同的文本越长，K取值越大。K的经验值参考，短文本K=5，长文本K=10 在这里插入图片描述

由上图所示，假设我们有四篇文档（4列），每篇文档的shingles如果出现则表示为1，否则为0。有了这个输入矩阵input_metrix，我们可以通过Jaccard方法计算文本的相似度： SIM ⁡ ( C i , C j ) = ∣ C i ∩ C j ∣ ∣ C i ∪ C j ∣ \operatorname{SIM}\left(C_{i}, C_{j}\right)=\frac{\left|C_{i} \cap C_{j}\right|}{\left|C_{i} \cup C_{j}\right|} SIM(Ci,Cj)=∣Ci∪Cj∣∣Ci∩Cj∣ 上式分子为两个文档之间交集，分母为两个文档的并集。拿上图举个例子，我们取文档1和文档2（列1和列2），他们之间的交集为2（即两列都为1的行数），并集为5（总共出现的nunique）。看到这里可能有人会提问为啥两列都为0的情况不计算？如果两列都为0，就表示这两篇文章都没有这个shingles，计不计算其实意义都不大。

有了Jaccard相似度，但是面对海量数据，高维 => 矩阵非常大的时候，我们的目标是需要找到一个Hash函数，将原来的Jaccard相似度计算，等同于降维后的相似度矩阵计算（Input Matrix => Signature Matrix）。

如果原来文档的Jaccard相似度高，那么它们的hash值相同的概率高。如果原来文档的Jaccard相似度低，那么它们的hash值不相同的概率高。

针对这个hash函数，聪明的人类提出了MiniHash。MiniHash需要准备两个东西：

Input Metrix随机置换表

下面上图：在这里插入图片描述上图中红黄蓝表示随机置换的顺序表，而右边的是输入矩阵Input Metrix。假设我们取蓝色的置换顺序表，那么我们通过置换可以得到以下的Metrix（如下图所示）。可以看到原本的第3行（0101）置换到了第1行，原本的第7行（1010）置换到了第3行。在这里插入图片描述

同样的，我们根据红色，黄色置换表，也可以得到不一样的Metrix。如下图所示的黄色置换表得到的Metrix。在这里插入图片描述有了三个置换的得到的Metrix后，重点来了。==对于每个metrix，我们取出每列首个为1的行数。==拿蓝色置换得到的矩阵为例（如下图），第1列首个1的行数为2，第2列首个1的行数为1，第3列为2，第4列为1，所以最终可以得到（2121）这个hash后的数值。在这里插入图片描述如此类推，由黄色+红色+蓝色的置换+hash后，可以得到以下的Signature Metrix。有了MiniHash得到的Signature Metrix，我们就可以计算Jaccard相似度了。如下图所示，第1行为原输入矩阵的Jaccard相似度，第2行为通过MiniHash降维后得到的Signature Metrix的Jaccard相似度。可以看出降维前后的相似度差距不是很大，但是两者之间的计算时间+空间量级得到了大大压缩。精度换时间，何乐而不为~ 在这里插入图片描述

MiniHash总结先将原矩阵Input Metrix分别经过n次随机置换（n取决于降维后的维度大小）。每次置换后，采用MinHash得到Signature Metrix。使用Sig矩阵相似度用来近似估计原始矩阵Input Matrix的Jaccard相似度。 MiniHash+LSH

当数据量非常大的时候，计算量随之也会成倍的增加。我们利用LSH+MiniHash的算法，将可能相似的用户以较大概率分到同一个桶内，这样每一个用户的“相似用户候选集”就会少很多，大大降低计算复杂度。其中主要的思想就是：

在MiniHash降维的基础上，将得到的Signature向量分成多段(band)。

将Signiture矩阵分成b组(即b个bands)，每组由r行组成。（如下图所示）在这里插入图片描述

对每一组进行hash，各个组设置不同的桶空间。只要两列有一组的MinHash相同，那么这两列就会hash到同一个桶而成为候选相似项.(如下图所示) 在这里插入图片描述对于以上分组，我们假设对于某行，两列MinHash的值相同的概率为s（两列的相似度），有：

在某个band，值都相等的概率是 S r S^r Sr

在某个band，值不相同的概率是 1 − S r 1-S^r 1−Sr

两个文档存在b个band，这b个band都不相同的概率是 ( 1 − S r ) b (1-S^r)^{b} (1−Sr)b

b个band里，至少有一个相同的概率是 1 − ( 1 − S r ) b 1-(1-S^r)^{b} 1−(1−Sr)b，即两列成为候选相似对的概率是 1 − ( 1 − S r ) b 1-(1-S^r)^{b} 1−(1−Sr)b。

以上我们将其称之为And Then Or方法，先要求每个band的所有对应元素必须都相同，再要求多个band中至少有一个相同。符合这两条，才能发生hash碰撞。下面我们举个例子用以理解：假设两列MinHash的值相同的概率s=0.8，20个band，每个band 5行，即b=20, r=5。有

在某个band，值都相等的概率： 0. 8 5 = 0.328 0.8^5 = 0.328 0.85=0.328在某个band，值不相同的概率： 1 − 0. 8 5 = 0.672 1- 0.8^5 = 0.672 1−0.85=0.672b个band都不相同的概率： 0.67 2 2 0 = 0.00035 0.672^20 = 0.00035 0.67220=0.00035b个band里，至少有一个相同的概率： 1 − 0.67 2 2 0 = 0.9996 1- 0.672^20 = 0.9996 1−0.67220=0.9996相应地，保持b和r不变，我们也可以调节不同的s，有：在这里插入图片描述

从上图可以看出，当我们的s超过某个阈值后，两个用户成为candidate用户的概率会迅速增加并接近于1。这个阈值，也就是概率变化最陡的地方，近似为 t = ( 1 b ) 1 r t=\left(\frac{1}{b}\right)^{\frac{1}{r}} t=(b1)r1 在这里插入图片描述

那么实际使用的过程中，我们需要确定以下几点：Smin，相似用户的阈值定义（近邻定义）Signature向量的长度，降到k维embedding，即随机置换表的个数。

而针对b和r的取值，我们需要考虑：

如果想要尽可能少的出现false negative，需要选择b和r使得概率变化最陡的地方小于Smin（比如s在0.5以上才属于相似用户，选择b和r使得S曲线的最陡处小于0.5）。在这里插入图片描述

如果想要保证计算速度较快，并且尽可能少出现false positive，那么最好选择b和r使得概率变化最陡的地方较大（比如b=20，r=6）这样，s较小的两个用户就很难成为candidate用户，但同时也会有一些“潜在”的相似用户不会被划分到同一个桶内。在这里插入图片描述

对于LSH的一般定义： Locality-Sensitive Hashing是满足一定条件的Hash函数簇令 d 1 d_1 d1= d 2 d_2 d2,则f(x)=f(y)的概率至多为 p 2 p_2 p2，即p(f(x)=f(y))

【本文地址】

RS推荐系统

RS推荐系统

今日新闻

推荐新闻